Khi Pyotr Đại đế dẫn quân đi đánh Azov của Đế chế Ottoman năm 1695, Gordon là một trong ba sư đoàn trưởng; hai người kia là Francis Lefort và Fyodor Alekseyevich Golovin. Không ai được cử làm tư lệnh cả chiến dịch. Điều này gây ra sự chia rẽ trong cấp chỉ huy – càng ngày càng trầm trọng. Cả Lefort và Golovin đều bực bội với Gordon và liên kết với nhau để bác lại ý kiến của Gordon dù ông có nhiều kinh nghiệm chiến trường hơn. Pyotr cũng mất kiên nhẫn, cùng với Lefort và Golovin quyết định mở cuộc tấn công nhằm tràn ngập thị trấn địch, nhưng Gordon cho rằng cần phải đào đường hào đến gần tường thành hơn để bảo vệ binh lính trước cuộc tấn công. Ý kiến của ông bị gạt ra một bên, và cuộc tấn công thất bại như đã được dự báo. Trong số 4 trung đoàn, 1.500 binh sĩ tử trận cùng một số sĩ quan.

Gordon lại tham gia chiến dịch đánh Azov năm sau, và lần này quân Nga thắng trận, chiếm được Azov.